package com.ting.test.algorithms.链表;

/**
 * 将单向链表按某值划分成左边小、中间相等、右边大的形式
 * 思路:
 * 1.把链表放入数组里，在数组上做partition（笔试用）
 * 这个问题就转换成了快排的问题了。
 */
public class 链表分区排列解法1 {
    public static void main(String[] args) {
        SingleNode node = new SingleNode();
        sort(node);
    }

    private static void sort(SingleNode head) {
        if (null == head || head.next == null) {
            return;
        }
        SingleNode[] arr = new SingleNode[20];

        SingleNode node = head;
        int index = 0;
        do {
            arr[index] = node;
            node = node.next;
            index++;
        } while (node != null);

        helan(arr, arr.length - 1);
    }


    private static void helan(SingleNode[] arr, int R) {
        int less = -1;
        int more = R;
        int index = 0;
        while (less < more) {
            if (arr[index].getValue() < arr[R].getValue()) {
                swap1(arr, index++, ++less);
            } else if (arr[index].getValue() == arr[R].getValue()) {
                index++;
            } else {
                swap1(arr, index, --more);
            }
        }
        swap1(arr, more, R);
    }

    private static void swap1(SingleNode[] arr, int A, int B) {
        SingleNode temp = arr[A];
        arr[A] = arr[B];
        arr[B] = temp;
    }
}
